<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*   
                a  b  c  b   a
                i            j
            ①：dp[i][j]:字符序列s(i,j)的最长回文子序列的长度为dp[i][j]
            ②：回文子序列其实也是自己跟自己比较，所以需要二维dp数组定义，且比较头尾
                if(s[i]==s[j])   dp[i][j]=dp[i+1][j-1]+2
                if(s[i]!=s[j])  
                如  a  b   c   b
                    i          j
                就继续比较 bcb  或者 abc
                dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1])

            ③确定遍历顺序
            因为dp[i][j]依赖于 dp[i+1][j-1]
            所以肯定是从下往上遍历,所以i=s.length-1
            同时，我们需要的是左右两边，所以要求j=i+1 初始化，j<i是无意义的
            
            ④初始化dp
            dp[i][i]=1
            */
            var longestPalindromeSubseq = function (s) {
                let dp = new Array(s.length).fill().map(() => new Array(s.length).fill(0))
                for (let i = 0; i < s.length; i++) {
                    dp[i][i] = 1
                }
                for (let i = s.length - 1; i >= 0; i--) {
                    for (let j = i + 1; j < s.length; j++) {
                        if (s[i] == s[j]) {
                            dp[i][j] = dp[i + 1][j - 1] + 2
                        } else {
                            dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1])
                        }
                    }
                }
                return dp[0][s.length - 1]
            }
        </script>
    </body>
</html>
